package com.lw.leetcode.bingChaJi.c;

/**
 * Created with IntelliJ IDEA.
 * 839. 相似字符串组
 * 剑指 Offer II 117. 相似的字符串
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/20 17:38
 */
public class NumSimilarGroups {

    public static void main(String[] args) {
        NumSimilarGroups test = new NumSimilarGroups();

        // 2
//        String[] arr = {"tars", "rats", "arts", "star"};

        // 1
//        String[] arr = {"omv", "ovm"};

        // 5
        String[] arr = {"kccomwcgcs", "socgcmcwkc", "sgckwcmcoc", "coswcmcgkc", "cowkccmsgc", "cosgmccwkc", "sgmkwcccoc", "coswmccgkc", "kowcccmsgc", "kgcomwcccs"};

        int i = test.numSimilarGroups(arr);
        System.out.println(i);
    }

    public int numSimilarGroups(String[] strs) {
        int length = strs.length;
        int[] arr = new int[length];
        for (int i = 0; i < length; i++) {
            arr[i] = i;
        }
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                arr[i] = find(arr, i);
                arr[j] = find(arr, j);
                if (check(strs[i], strs[j])) {
                    arr[arr[j]] = arr[i];
                }
            }
        }
        for (int i = length - 1; i >= 0; i--) {
            find(arr, i);
        }
        int count = 0;
        for (int i = length - 1; i >= 0; i--) {
            if (arr[i] == i) {
                count++;
            }
        }
        return count;
    }

    private int find(int[] arr, int t) {
        if (arr[t] == t) {
            return t;
        }
        arr[t] = find(arr, arr[t]);
        return arr[t];
    }

    private boolean check(String a, String b) {
        int length = a.length();
        int c = 0;
        for (int i = 0; i < length; i++) {
            if (a.charAt(i) != b.charAt(i)) {
                c++;
            }
            if (c > 2) {
                return false;
            }
        }
        return true;
    }

}
